【数据结构笔记】顺序表——动态数组

查看原文

其他

【数据结构笔记】顺序表——动态数组

Original 正念君嵌入式大杂烩 2021-01-31

收录于话题

#C语言笔记

53个

这篇写的是顺序表——动态分配。关于顺序表的具体描述可看上一篇文章写的是顺序表——静态分配。

顺序表的操作（用动态分配实现）

1、顺序表的结构定义

2、创建一个顺序表：（5，2，0，13，14）

3、查找操作

4、替换旧元素old_elem为新元素new_elem

5、替换位置pos上的数据为elem

6、插入操作

7、删除操作

8、销毁函数

程序运行结果：

/*----------------------------------------------------------------------------------------
  
  程序说明：顺序表（动态分配）
    创建日期：2018.12.09 by LiZhengNian

----------------------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

/* 数据元素类型 */
typedef int SqType;

/* 顺序表的结构定义 */
typedef struct Sqlist
{
  SqType *elem;  // 定义一个动态数组elem
  int length;    // 顺序表的长度
  int size;      // 顺序表的存储容量
}Sqlist;

/* 函数的声明 */
Sqlist init_list(void);                                      // 初始化顺序表
void printf_list(Sqlist l);                                  // 打印顺序表
int serch(Sqlist l, SqType elem);                // 查找元素位置  
Sqlist replace_elem(Sqlist l, SqType old_elem, SqType new_elem);// 替换旧元素old_elem为新元素new_elem
Sqlist replace_pos(Sqlist l, int pos, SqType elem);        // 替换位置pos上的元素为elem
Sqlist insert(Sqlist l, int pos, SqType elem);          // 插入新元素
Sqlist delete(Sqlist l, int pos);                // 删除元素
void destroy_list(Sqlist l);                    // 销毁顺序表


int list[SIZE] = {5, 2, 0, 13, 14};  // 用于初始化顺序表
/*******************************************************************************************************
** 函数: main，主函数
**------------------------------------------------------------------------------------------------------
** 参数: void
** 返回: 无
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
int main(void)
{
  Sqlist l;
  int pos = 0;
  int serch_elem = 13;
  
  /* 创建一个顺序表：(5, 2, 0, 13, 14) */
  l = init_list();
  printf("创建的顺序表为：");
  printf_list(l);
  
  /* 把旧元素0替换为新元素1 */
  l = replace_elem(l, 0, 1);
  printf("把0替换为1得到的新顺序表为：");
  printf_list(l);  
  
  /* 把第1个位置上的元素改为10 */
  l = replace_pos(l, 1, 10);
  printf("第一个位置改为10得到的新顺序表为：");
  printf_list(l);    
  
  /* 往第二个位置插入新元素99 */
  l = insert(l, 2, 99);
  printf("第二个位置插入99得到的新顺序表为：");
  printf_list(l);    
  
  /* 删除第二个位置上的元素 */
  l = delete(l, 2);
  printf("删除第二个位置元素得到的新顺序表为：");
  printf_list(l);    
  
  /* 查找serch_elem在该顺序表l中的第几个位置 */
  pos = serch(l, serch_elem); 
  printf("元素%d在顺序表的第%d个位置\n", serch_elem, pos);
  
  /* 销毁顺序表 */
  printf("\n销毁顺序表\n");
  destroy_list(l);
  
  return 0;
}

/*******************************************************************************************************
** 函数: create_list，创建一个顺序表
**------------------------------------------------------------------------------------------------------
** 参数: void
** 返回: 创建成功的顺序表
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist init_list(void)
{
  Sqlist l;
  int i;
  
  l.elem = (SqType*)malloc(SIZE*sizeof(SqType)); // 动态申请空间
  if(!l.elem) //如果申请失败，作出提示并直接退出程序
  {
    printf("%s:申请动态内存失败!\n",__FUNCTION__);
    exit(0);  // 退出程序
  }
  
  for (i = 0; i < SIZE; i++)
  {
    l.elem[i] = list[i];
  }
  l.length = SIZE;  // 此时顺序表表长为SIZE
  l.size = SIZE;    // 此时顺序表占的的存储单元个数为SIZE
  
  return l;
  
}

/*******************************************************************************************************
** 函数: serch，查找元素elem在顺序表l的第几个位置
**------------------------------------------------------------------------------------------------------
** 参数: l：顺序表   elem：要查找的元素
** 返回: pos：元素elem的位置  -1：查找失败
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
int serch(Sqlist l, SqType elem)
{
  int i;
  int pos = 0;
  
  for (i = 0; i < l.length; i++)
  {
    if (elem == l.elem[i])
    {
      pos = i + 1;
      return pos;  // 查找成功
    }
  }
  
  return -1;  // 查找失败
}

/*******************************************************************************************************
** 函数: replace_elem，把旧元素old_elem替换为新元素new_elem
**------------------------------------------------------------------------------------------------------
** 参数: l：顺序表  old_elem：旧元素  new_elem：新元素
** 返回: 替换完成后的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist replace_elem(Sqlist l, SqType old_elem, SqType new_elem)
{
  int old_elem_pos;
  
  old_elem_pos = serch(l, old_elem);  // 首先查找旧元素所在的位置
  l.elem[old_elem_pos - 1] = new_elem;
  
  return l;   // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: replace_pos，把第pos个位置上的元素替换为elem
**------------------------------------------------------------------------------------------------------
** 参数: l：顺序表  pos：位置  elem：元素
** 返回: 替换完成后的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist replace_pos(Sqlist l, int pos, SqType elem)
{
  l.elem[pos - 1] = elem;
  
  return l; // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: insert，把元素elem插入到顺序表l的第pos个位置
**------------------------------------------------------------------------------------------------------
** 参数: l：顺序表  pos：位置  elem：元素
** 返回: 插入元素后得到的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist insert(Sqlist l, int pos, SqType elem)
{
  int i;
  /* 判断插入的位置是否存在、是不是超过了表的长度 */
  if (pos < 1 || pos > l.length)
  {
    printf("%s:插入错误！\n", __FUNCTION__);
    return l;
  }
  /* 插入新元素，因此需要重新申请内存 */
  if (l.length >= l.size)
  {
    l.elem = (SqType*)realloc(l.elem, (l.size+1)*sizeof(SqType));
    if (!l.elem)
    {
      printf("%s:重新申请动态内存失败!\n",__FUNCTION__);
      exit(0);  // 退出程序
    }
    l.size += 1;
  }
  l.length += 1;  // 插入一个新元素，表长加一
  /* 从第pos个位置开始所有元素往后移一个元素长度 */ 
  for (i = l.length - 1; i >= pos-1; i--)
  {
    l.elem[i+1] = l.elem[i];
  }
  
  l.elem[pos-1] = elem; // 插入的新元素
  
  return l;  // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: delete，把第pos个位置的元素删除
**------------------------------------------------------------------------------------------------------
** 参数: l：顺序表  pos：位置 
** 返回: 删除元素后得到的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist delete(Sqlist l, int pos)
{
  int i;
  /* 判断要删除的位置是否存在、是不是超过了表的长度 */
  if (pos < 1 || pos > l.length)
  {
    printf("%s:删除位置错误！\n", __FUNCTION__);
    return l;
  }
  
  /* 从第pos个位置开始所有元素前移一个元素长度 */
  for (i = pos-1; i < l.length; i++)
  {
    l.elem[i] = l.elem[i+1];
  }
  
  l.length -= 1;  // 删除一个元素后表长减一
  
  return l;  // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: destroy_list，销毁顺序表
**------------------------------------------------------------------------------------------------------
** 参数: l：要销毁的顺序表
** 返回: void
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
void destroy_list(Sqlist l)
{
  free(l.elem);  // 释放动态内存，防止内存泄漏
  l.elem = NULL;  // 防止出现野指针
}

/*******************************************************************************************************
** 函数: printf_list，打印输出顺序表
**------------------------------------------------------------------------------------------------------
** 参数: l：顺序表  pos：位置 
** 返回: 删除元素后得到的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
void printf_list(Sqlist l)
{
  int i;
  for(i = 0; i < l.length; i++)
  {
    printf("%d ",l.elem[i]);
  }
  printf("(表长为%d)", l.length);
  printf("\n\n");
}